package com.mashibing.class02;

import java.util.HashMap;
import java.util.HashSet;

public class Code03_KM {

    public static int test(int[] arr,int k, int m){
        HashMap<Integer,Integer> map = new HashMap<Integer, Integer>();
        for (int num : arr) {
            if (map.containsKey(num)){
                map.put(num,map.get(num));
            }else {
                map.put(num,1);
            }
        }

        for (Integer num : map.keySet()) {
            if (map.get(num)==k){
                return num;
            }
        }
        return -1;
    }

    public static int[] randomArray(int maxKinds,int range,int k, int m){
        int ktimeNum = (int) (Math.random()*range);

        int times = Math.random() < 0.5 ? k :((int) (Math.random()*(m-1))+1);

        int numKinds = (int) (Math.random()*maxKinds) +2;
        int[] arr = new int[times+(numKinds-1)*m];
        int index = 0;
        for(;index<times;index++){
            arr[index] = ktimeNum;
        }
        numKinds--;
        HashSet<Integer> set = new HashSet<Integer>();
        set.add(ktimeNum);
        while (numKinds!=0){
            int curNum = 0;
            do {
                curNum = randomNumber(range);
            }while (set.contains(curNum));
            set.add(curNum);
            numKinds--;
            for (int i=0;i<m;i++){
                arr[index++] = curNum;
            }
        }
        // arr 填好了.
        for (int i = 0; i < arr.length; i++) {
            // i 位置的数 我想随机和j位置的数交换
            int j = (int) (Math.random()* arr.length);
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        return arr;
    }
    
    //[-range, +range]
    public static int randomNumber(int range){
        return (int) (Math.random()*range+1) - ((int) (Math.random()*range)+1);
    }

    // 请保证arr中, 只有一种数出现了K次, 其他数都出现了M次.
    public static int onlyTimes(int[] arr,int k,int m){
        int[] t = new int[32]; // 定义一个词频统计变量 t.
        //t[0] 0位置的1出现了几个
        //t[i] i位置的出现了几个
        for (int num : arr) {
            for (int i = 0; i <= 31; i++) {
//                if (((num>>i)&1)!=0){ // 此时就代表num在第i位上是1
//                    t[i]++;
//                }
                t[i] += (num>>i)&1;
            }
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            if (t[i]%m==0){ //这种值在第i位是不包含1的.
                continue;
            }
            if(t[i]%m==k){ //这种值在第i位是包含1的.
                ans |= (1<<i);
            }else {
                return  -1;
            }
        }
        if (ans == 0) {
            int count = 0;
            for (int num : arr) {
                if (num==0){
                    count++;
                }
            }
            if (count!=k){
                return -1;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
       int kind = 4;
       int range = 200;
       int testTime = 100000;
       int max = 9;
        for (int i = 0; i < testTime; i++) {
            int a = (int) (Math.random()*max)+1; // a 1-9
            int b = (int) (Math.random()*max)+1; // b 1-9
            int k = Math.min(a,b);
            int m = Math.max(a,b);
            if (k==m){
                m++;
            }
            int[] arr = randomArray(kind,range,k,m);
            int ans1 = test(arr,k,m);
            int ans2 = onlyTimes(arr,k,m);
            if (ans1 != ans2){
                System.out.println("ans1 = " + ans1);
                System.out.println("ans2 = " + ans2);
                System.out.println("出错了!!");
            }
        }
        System.out.println("测试结束!!");
    }
}
